/*
 * Miccsnookersim, a snooker simulation with AI
 * Copyright (C) 2009 Enno Ruijters, Frans van den Heuvel, Yannick Thimister,
 * Ali B. Ozmen, Esther Verhoef, Achim Leydecker
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.

 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
import java.util.*;
import java.util.concurrent.atomic.*;
import java.awt.Color;
import java.lang.Thread;
 
public class TacticalAI implements Player
{
	private class CollisionData
	{ /* Why can't java have structs like any sane language */
		public static final byte COLL_EDGE = 1;
		public static final byte COLL_STAT_BALL = 2;
		public static final byte COLL_MOV_BALL = 3;
		public Vector position;
		public Ball ball;
		public Ball otherBall; /* Only set if type != COLL_EDGE */
		public double vRelative;
		public Vector otherPosition;
		public byte collisionType;
	}

	private class Listener implements TableListener
	{
		private LinkedList<CollisionData> collisions;
		private HashMap<Ball, Vector> pottedBalls;

		public Listener()
		{
			collisions = new LinkedList<CollisionData>();
			pottedBalls = new HashMap<Ball, Vector>();
		}
		public void gameEnd() { }
		public void shotBegin() { }
		public void ballCollision(Ball a, Object o)
		{
			byte type;
			CollisionData c = new CollisionData();
			c.position = a.getPosition().clone();
			if (o instanceof Ball) {
				Ball b = (Ball) o;
				c.otherPosition = b.getPosition().clone();
				c.otherBall = b;
				if (b.getVelocity().magnitude() != 0
				    && a.getVelocity().magnitude() != 0)
					type = CollisionData.COLL_MOV_BALL;
				else
					type = CollisionData.COLL_STAT_BALL;
				c.vRelative = Vector.subtract(a.getVelocity(),
				                              b.getVelocity())
				                                   .magnitude();
			} else {
				c.vRelative = a.getVelocity().magnitude();
				type = CollisionData.COLL_EDGE;
			}
			c.collisionType = type;
			c.ball = a;
			collisions.add(c);
		}

		public void ballPocketed(Ball b)
		{
			pottedBalls.put(b, b.getPosition().clone());
		}
		public void shotEnd() { }
		public List<CollisionData> getCollisions()
		{
			return collisions;
		}
		public HashMap<Ball, Vector> getPottedBalls()
		{
			return pottedBalls;
		}
	}

	private static final int DEFAULT_NUM_SAMPLES = 3000;
	private static final int NUM_THREADS = 4;
	private static final double MAX_ALLOWED_DISTANCE = 500;
	private static final float SNOOKER_POINTS = 0.4f;
	private static final float KEEP_TURN_THRESHOLD = 0.2f;
	/* With how many computed points do we expect to keep the turn */
	private int numSamples;
	private Table table;
	private String name;
	private Thread[] activeThreads;
	
	/**
		Creates an instance of the AI
		@param samples How many random samples to try
		@param g The Table to play on
		@param name The name of this AI
	*/
	public TacticalAI(int samples, Table g, String name)
	{
		numSamples = samples;
		table = g;
		this.name = name;
	}
	
	/**
		Creates an instance of the Ai with the default setting for the amount of samples
		@param g The Table to play on
		@param name The name of this AI
	*/
	public TacticalAI(Table g, String name)
	{
		this(DEFAULT_NUM_SAMPLES, g, name);
	}

	private class ShotData
	{
		public Cue shot;
		public double score;
		public Vector cueBallPosition;
		public ShotData()
		{
			score = Double.NEGATIVE_INFINITY;
			shot = null;
			cueBallPosition = null;
		}
	}
	
	private class Evaluator implements Runnable
	{
		private AtomicInteger shotsLeft;
		private ShotData shotReturn;
		private Table table;
		private Ball cueBall;
		private Random generator;

		public Evaluator(AtomicInteger numShots, ShotData shotReturn,
		                 Table t, long randomSeed)
		{
			shotsLeft = numShots;
			this.shotReturn = shotReturn;
			table = t;
			generator = new Random(randomSeed);
			for (Ball b : table.getBalls())
			{
				if (b.getColor() == Color.WHITE)
				{
					cueBall = b;
				}
			}
			assert(cueBall != null);
		}

		public void run()
		{
			Cue bestShot = null; // the best of the best
			float best = Float.NEGATIVE_INFINITY;
			Vector bestPosition = null;
			/* I hope you can't get an infinite number of penalty
			 * points somehow
			 */
			int optimal;

			if(table.getGameLogic().getColouredOn()) {
				if (table.getGameLogic().inFinalMode())
					optimal = 1;
				else
					optimal = 7;
			} else {
				optimal = 1;
			}

			while(shotsLeft.getAndDecrement() > 0 && best < optimal)
			{
				Cue currentShot = new Cue();
				Vector newPosition = null;
				if (cueBall.getPosition().magnitude() == Double.POSITIVE_INFINITY) {
					newPosition = new Vector(Table.createBaulkLine().getX1(), (Table.createBaulkLine().getY1() + Table.createBaulkLine().getY2()) / 2, 0);
					Vector offset = new Vector(Math.random() * Table.getTableWidth() / 12, 0, 0);
					offset.rotate_(generator.nextDouble() * Math.PI - Math.PI / 2); /* Max rotation 1/2 PI */
					newPosition.add_(offset);
					newPosition = new Vector(285,100,0);
				}
			
				Vector force = new Vector(
				                   generator.nextInt(800) - 400,
				                   generator.nextInt(800) - 400,
				                   0);
				currentShot.setForce(force); //random amount of force (between 100 and 500)
			
				Vector v = new Vector(0, Ball.RADIUS, 0);
				v = v.rotateAroundX_(generator.nextDouble() * Math.PI / 2);
				v = v.rotate_(Math.random() * Math.PI / 2);
				//Rotate the Cueshot randomly around the ball 
				if (newPosition == null)
					v.add_(cueBall.getPosition());
				else
					v.add_(newPosition);
				currentShot.setPosition(v);
			
				/* Shot evaluation */
				float points = evaluate(currentShot, table, newPosition);
				if(points > best)
				{
					bestShot = currentShot;
					best = points;
					bestPosition = newPosition;
					System.out.println("Best shot : " + best);
				}
			}
			synchronized(shotReturn) {
				if (shotReturn.score < best) {
					shotReturn.score = best;
					shotReturn.shot = bestShot;
					shotReturn.cueBallPosition = bestPosition;
				}
			}
		}
	}

	/* I'm a bit worried threading overhead might kill us, but it's simpler
	 * to implement like this than to keep threads on standby.
	 */
	public Cue getShot()
	{
		ShotData bestShot = new ShotData();
		AtomicInteger numShots = new AtomicInteger(numSamples);
		Evaluator[] evaluators = new Evaluator[NUM_THREADS];
		for (int i = 0; i < NUM_THREADS; i++)
			evaluators[i] = new Evaluator(numShots, bestShot, table,
			                        System.currentTimeMillis() + i);
		synchronized(this) {
			activeThreads = new Thread[NUM_THREADS];
			for (int i = 0; i < NUM_THREADS; i++) {
				activeThreads[i] = new Thread(evaluators[i]);
				activeThreads[i].start();
			}
		}
		for (int i = 0; i < NUM_THREADS; i++) {
			try {
				activeThreads[i].join();
			} catch (Exception e) {
				System.out.println("Something killed one of our"
				                   + " calculated threads.");
			}
		}
		if (bestShot.shot == null) {
			/* All our threads were prematurely interrupted, so we
			 * just do the calculation single-threaded.
			 */
			numShots.set(numSamples);
			evaluators[0].run();
		}
		System.out.format("Final best shot: %f\n", bestShot.score);
		if (bestShot.cueBallPosition != null) {
			Ball cueBall = null;
			for (Ball b : table.getBalls())
			{
				if (b.getColor() == Color.WHITE)
				{
					cueBall = b;
				}
			}
			cueBall.setPosition(bestShot.cueBallPosition);
			table.replaceBall(cueBall);
		}
		return bestShot.shot;
	}

	/**
		Evaluates a shot.

		This is actually thread-safe.
		@param shot the shot to evaluate
		@param table the Table on which the shot should be evaluated
		@param cueBallPosition the place on the table where the cue
		ball should be replaced (only useful if the ball is off of
		the table to begin with.
		@return Integer indicating the value of the last shot (higher = better)
	*/
	private float evaluate(Cue shot, Table table, Vector cueBallPosition) 
	{
		float ret;
		int easyBallsBeforeShot = table.numEasyBalls();
		boolean appliedSnooker = false;
		Table tmpTable = table.clone();
		Listener listener = new Listener();
		if (cueBallPosition != null) {
			Ball cueBall = null;
			for (Ball b : tmpTable.getBalls())
			{
				if (b.getColor() == Color.WHITE)
				{
					cueBall = b;
				}
			}
			assert(cueBall.getPosition().magnitude() >= 1.0/0.0);
			cueBall.setPosition(cueBallPosition.clone());
			tmpTable.replaceBall(cueBall);
		}
		tmpTable.addListener(listener);
		Simulation sim = new Simulation(tmpTable);
		sim.performShot(shot, false, false);
		HashMap<Ball, Vector> usefulBalls = listener.getPottedBalls();
		ret = tmpTable.getGameLogic().getPointsLastShot();
		if (tmpTable.getGameLogic().isSnookered()) {
			Ball cueBall = null;
			for (Ball b : tmpTable.getBalls())
				if (b.getValue() == 0)
					cueBall = b;
			if (ret <= 0) {
				ret += SNOOKER_POINTS;
				appliedSnooker = true;
				usefulBalls = new HashMap<Ball, Vector>();
			}
			usefulBalls.put(cueBall, cueBall.getPosition().clone());
		}
		boolean hadBallCollisions = false;
		ListIterator<CollisionData> iter;
		iter = listener.getCollisions().listIterator(listener.getCollisions().size());
		while (iter.hasPrevious()) {
			double distance = 0;
			CollisionData c = iter.previous();
			if (c.collisionType == CollisionData.COLL_EDGE) {
				Vector oldPosition = usefulBalls.remove(c.ball);
				if (oldPosition == null)
					continue;
				usefulBalls.put(c.ball, c.position);
				distance = Vector.subtract(oldPosition,
				                        c.position).magnitude();
				distance += c.vRelative / 4;
			} else {
				Vector posA = usefulBalls.remove(c.ball);
				Vector posB = usefulBalls.remove(c.otherBall);
				Vector tmp;
				if (posA == null && posB == null) {
					/* Not a useful collision */
					continue;
				}
				usefulBalls.put(c.ball, c.position);
				usefulBalls.put(c.otherBall, c.otherPosition);
				if (posA != null) {
					tmp = Vector.subtract(posA, c.position);
					distance = tmp.magnitude();
				}
				if (posB != null) {
					tmp = Vector.subtract(posB,
					                      c.otherPosition);
					distance += tmp.magnitude();
				}
				distance += c.vRelative / 4;
			}
			switch (c.collisionType) {
			case CollisionData.COLL_EDGE:
				ret *= 0.9;
				break;
			case CollisionData.COLL_MOV_BALL:
				ret *= 0.5;
			case CollisionData.COLL_STAT_BALL:
				ret *= 0.85;
				hadBallCollisions = true;
				break;
			}
			if (distance > MAX_ALLOWED_DISTANCE)
				ret = 0;
			else
				ret *= 1.0 - (distance / MAX_ALLOWED_DISTANCE);
		}
		if (tmpTable.numEasyBalls() > easyBallsBeforeShot) {
			double factor = 0.2 * (tmpTable.numEasyBalls() - easyBallsBeforeShot);
			if (ret > KEEP_TURN_THRESHOLD)
				ret += factor;
			else
				ret -= factor;

		} else {
			if (ret > KEEP_TURN_THRESHOLD)
				ret *= Math.pow(0.8, easyBallsBeforeShot - tmpTable.numEasyBalls());
			else
				ret /= Math.pow(0.8, easyBallsBeforeShot - tmpTable.numEasyBalls());
		}
		if (hadBallCollisions)
			ret /= 0.85; /* Cue ball hit should not cost points */
		if (!appliedSnooker && tmpTable.getGameLogic().isSnookered()) {
			if (ret < KEEP_TURN_THRESHOLD)
				ret += SNOOKER_POINTS;
			else
				ret -= SNOOKER_POINTS;
				/* We should not snooker ourselves */
		}

		return ret;
	}
	
	/* Can be called concurrently */
	public synchronized void replaceCueBall(Table t, Ball cueBall)
	{
	}

	public String getName()
	{
		return name;
	}

	public synchronized void terminate()
	{
		if (activeThreads != null) {
			for (Thread t : activeThreads)
				t.stop();
		}
	}

	public void setTable(Table newTable)
	{
		table = newTable;
	}
}
